题解 AT4164@洛谷 | 4164@Atcoder 【[ABC102A] Multiple of 2 and N】

题意:求输入的数和 22lcm\text{lcm}

这里根据数学证明可得:lcm(a,b)=a/gcd(a,b)blcm(a, b)=a/\gcd(a, b)*b,而 gcd\gcd 可以通过辗转相除法计算。以下给出 Python3\text{Python3}C++\text{C++} 的程序以及伪代码。

Python3:

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x%y)

def lcm(x, y):
    if x < y:
        z = x
        x = y
        y = z
    return x / gcd(x, y) * y

print(int(lcm(int(input()), 2)))

C++:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    cout<<n/__gcd(max(2, n), min(2, n))*2<<endl;
    return 0;
}

伪代码:

int gcd(x, y):
    if y==0:
        return x
    return gcd(y, x mod y)

int lcm(x, y):
    if x < y:
        swap x ↔ y
    return x/gcd(x, y)*y

input n
print lcm(n, 2)